Let G = (V, E) be a graph representing a network, where V is the set of N nodes and E is the set of M connections. M is the total number of edges in the network. We denote the network community structure as C = {C₁, C₂,..., C_k}. k_i is the degree of vertex v_i, is the number of edges the vertex v_i connecting to the community of C_i, and is the total number of edges with the vertex v_i connecting to other communities. We allow C_i ∩ C_j ≠ ϕ so that the network communities can overlap with each other. A neighborhood set N(v_i) is the collection of neighboring nodes of vertex i (v_i). N(C) is the collection of neighboring nodes of community C.

Our objective is to find the seed communities of networks which are more distant from each other and extend the seeds. In networks, the connection crossings between communities should be less than those inside them.^[13] Unlike the case of disjoint community structures, overlapping communities allow a node to belong to more than one community. In this paper, we use three functions to realize the process of community detection.

First, in order to save the running time, we will find all nodes whose degrees are greater than the average of the network, and organize them into a set S in descending order. By doing this, we can filter out some important nodes. Then we select the v_i (v_i ∈ S) which has the maximum degree and has not been assigned to the seeds of communities as the seed of absorbing community. Because S is ordered, v_i is the first node in S. If the vertex v_j meets the following condition, traverse S and absorb the vertex v_j ∈ S until no more nodes can be absorbed.

Definition 2 suggests that there are enough public neighbors between v_i and v_j. Then we can make a judgment that they have a much closer relationship with each other than with others. Let us assume that v_i and v_j are not in the same community. Because of the condition I(v_i) ∩ I(v_j) ≥ I(v_j)/2(i ≤ j), the vertex v_i is closer with another community which contains v_j, which is consistent with the definition of community.

In order to explain the process of selecting the core vertex and the seed of absorbing community, Zachary’s network of karate club members is considered in Fig. 1, from which we can see the average degree of the network is 5 (the accurate value is 4.6, here we round it up to an integer) and the S is {34, 1, 33, 3, 2, 4, 32, 9, 14, 24}. Then we choose the node v_i = {34} as the seed of the absorbing community C₁, C₁ = C₁ ∪ v_i. Now the set of S = {1, 33, 3, 2, 4, 32, 9, 14, 24}. Table 1 is the analysis process of finding the seed communities of Zachary’s network. Through the pretreatment of vital nodes, we can get two seed communities {34, 33, 3, 32, 9, 24} and {1, 2, 4, 14}.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. (color online) Two communities and four overlapping vertices in friendship network from Zachary’s karate club study.

However, the community structure is not always strongly related with nodes of large degree. For example, the community in power grid can be composed of nodes with homogeneous degrees. For this type of network, our approach is still applicable. For example, figure 2 is a simple network, where nodes have relatively homogeneous degrees. In this case, the set of S will include most of the nodes in the network, S = {2, 4, 3, 5, 6, 7, 8, 9}. We can still obtain some seeds of communities, {2, 4, 3, 5, 6} and {7, 8, 9}. Meanwhile, because we have dealt with sufficient nodes, the following processing time will be greatly shortened. There are still some defects when we deal with tree like and household networks.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. (color online) A simple network where nodes have relatively homogeneous degrees.

Table 1.

Table 1.

Table 1. Analysis of the process of finding the seed communities of Zachary’s network. . vi vj S Seed communities Round 1 34 {1, 33, 3, 2, 4, 32, 9, 14, 24} C1 = {34} 34 1 I(vi) ∩ I(vj) < I(vj)/2 {1, 33, 3, 2, 4, 32, 9, 14, 24} C1 = {34} 34 33 I(vi) ∩ I(vj) ≥ I(vj)/2 {1, 3, 2, 4, 32, 9, 14, 24} C1 = {34, 33} 34 3 I(vi) ∩ I(vj) ≥ I(vj)/2 {1, 2, 4, 32, 9, 14, 24} C1 = {34, 33, 3} 34 2 I(vi) ∩ I(vj) < I(vj)/2 {1, 2, 4, 32, 9, 14, 24} C1 = {34, 33, 3} 34 4 I(vi) ∩ I(vj) < I(vj)/2 {1, 2, 4, 32, 9, 14, 24} C1 = {34, 33, 3} 34 32 I(vi) ∩ I(vj) ≥ I(vj)/2 {1, 2, 4, 9, 14, 24} C1 = {34, 33, 3, 32} 34 9 I(vi) ∩ I(vj) ≥ I(vj)/2 {1, 2, 4, 14, 24} C1 = {34, 33, 3, 32, 9} 34 14 I(vi) ∩ I(vj) < I(vj)/2 {1, 2, 4, 14, 24} C1 = {34, 33, 3, 32, 9} 34 24 I(vi) ∩ I(vj) ≥ I(vj)/2 {1, 2, 4, 14} C1 = {34, 33, 3, 32, 9, 24} Round 2 1 {2, 4, 14} C2 = {1} 1 2 I(vi) ∩ I(vj) ≥ I(vj)/2 {4, 14} C2 = {1, 2} 1 4 I(vi) ∩ I(vj) ≥ I(vj)/2 {14} C2 = {1, 2, 4} 1 14 I(vi) ∩ I(vj) ≥ I(vj)/2 ϕ C2 = {1, 2, 4, 14}

Table 1. Analysis of the process of finding the seed communities of Zachary’s network. .

Second, we will extend the seed communities. It is shown that most setting ranges of parameters related to the intimacy between nodes and communities are too strict in the searching process. As shown in Fig. 3, by calculating the absorbing degree A(C_i, μ) in Ref. [7] and the fitness function in Ref. [18], we can get A(C₁, μ) ˃ A(C₂, μ) and the fitness and . Therefore, the node μ is categorized into the community of C₁. But in reality, especially when the difference of two link weights between μ and two communities is very small, we will take the node as a common node. To solve this problem, we put forward a new parameter to measure the intimacy between the node and the community. For a community C_i and a node μ, the attribution degree α(C_i, μ) between C_i and μ is defined as

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. (color online) A simple example discussing the question of belongingness.

It reflects how tight the node μ is with community C_i. is the number of edges between μ and community C_i, and is the number of edges between μ and others. The attribution degree α(C_i, μ) reflects the ratio of the difference between the inner and outer edges of μ and C_i to the total degrees of μ. If α(C_i, μ) < 1, we will consider that the node μ belongs to the community C_i. Then, in Fig. 3, we can easily get α(C₁, μ) < 1 and α(C₂, μ) < 1. The node μ is the common node. Therefore, in this case, the attribution degree α(C_i, μ) is more reasonable.

For the unassigned nodes, we will consider the fitness function^[18]

In order to quantify the community structure of a network, Newman and Girvan^[19] proposed the modularity Q as a measure of network partition

The detection of the seeds of communities is the first and also the most important phase of our method. Generally speaking, the seeds of communities provide us an overview of the network as well as the critical information of communities. First, we will get the set of vital nodes S through the pretreatment of V where the degree of every node is greater than the average degree of network, which can effectively reduce the number of nodes that need to be treated. And S is an ordered collection where nodes are sorted in descending order by degree. It is worth mentioning that a node in S belongs to only one club. For example, consider Zachary’s network of karate club members in Fig. 1, we can get S = {34, 1, 33, 3, 2, 4, 32, 9, 14, 24}, and two seeds of communities {34, 33, 3, 32, 9, 24} and {1, 2, 4, 14} will be found through Algorithm 1.

The details are presented in Algorithm 1.

During the experiment, we find that the condition of I(S[0]) ∩ I(u) ≥ I(u)/2 is so severe that too many nodes are divided into a club alone. So by relaxing the condition, we add another condition that u is in the same community with S[0] when they have a complete subgraph between u, S[0], and at least two common neighbor nodes of them. The experimental results show that additional condition does not have any effect on previous condition, nor does it obtain better experimental results.

As soon as the first procedure finishes, the raw network community structure can be pictured as a collection of dense parts of the network together with outliers. Because of the condition setting in step 1, there is a low overlapping score between the two seeds. Then we just need to extend the seed communities.

For Zachary’s network, because two seeds of communities {34, 33, 3, 32, 9, 24} and {1, 2, 4, 14} have been found through Algorithm 1, we can get N(C₁) = {1, 2, 4, 8, 10, 14, 15, 16, 19, 20, 21, 23, 25, 26, 27, 28, 29, 30, 31} and N(C₂) = {5, 6, 7, 8, 9, 11, 12, 13, 18, 20, 22, 31, 32, 34}. Then we will get the community structure like Fig. 1. We also analyze the network in Fig. 2 and get two communities {1, 2, 3, 5, 6} and {6, 7, 8, 9, 10}. Vertex 6 is the common node. All nodes of these two networks are divided into the community they should belong to. As a result, the Algorithm 3 will be skipped.

Even when the above two procedures are executed, there will still be remaining nodes due to their less attraction to the rest of the network. Therefore, we need to revisit these nodes. Here, we use the fitness function to quantify the similarity between a node u and a neighbor community C. Fitness function is described as

The detailed description is presented in Algorithm 3.

First, we should take at least O(n logⁿ) to sort the vertices by degree. Then in the average case, the number of nodes we choose in S is the half of V. So, the average time complexity of Algorithm 1 is O(n²/8), and the total complexity of Algorithm 2 and Algorithm 3 is about O(m). At the worst, it costs O(nlogⁿ + n²/8 + m) to find all communities.

The well-known karate club study of Zachary^[26] is widely used as a test case for new methods in complex networks. It consists of 34 members of a karate club as vertices and 78 edges representing friendships among members of the club. By chance, a dispute arose between the club’s administrator and the club’s instructor, and as a result, the club eventually split into two smaller clubs, centered on the administrator and the instructor.^[20] The network and its fission are depicted in Fig. 4. The administrator and the instructor are represented by node 1 and node 33, respectively.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. (color online) Two communities and four overlapping vertices in friendship network from Zachary’s karate club study.

As shown in Fig. 4, two overlapping communities with four nodes 3, 14, 9, and 31 in common are detected by our method, with Q₀ = 0.332. In Ref. [27], there are two communities and five common nodes, which include nodes 3, 9, 10, 14, and 31. This network is also discussed in other methods, and further details are provided in Table 2. Consistent with the real split, our algorithm finds two communities. Although we have found four common nodes which are different from the reality, it is reasonable to regard them as common nodes of the two communities.

It describes the associations between 62 dolphins living in Doubtful Sound, New Zealand, with ties between dolphin pairs being the statistically significant frequent association.^[20] This network can be split naturally into two groups. But in this paper, we find four communities by our algorithm, which are represented by different colors in Fig. 5. The modularity of dolphin’s network calculated by our method is 0.511. In the EM-BOAD algorithm of Ref. [7] and the GN algorithm of Ref. [16], this network splits into three communities and two large communities with modularity Q₀ of 0.457 and modularity Q of 0.38, respectively.

Fig. 5.

	Figure Option ViewDownloadNew Window
	Fig. 5. (color online) Communities in dolphin’s living network (no common node is found in this network).

The third network instance is the college football games in division IA in USA in the fall of 2000,^[8] which is a network representing the schedule of games between American college football teams. It includes 115 teams from 12 conferences, and 616 edges represent regular season games. The Chen algorithm^[27] splits the network into 13 non-overlapping communities. 10 non-overlapping communities are detected by our algorithm, as shown in Fig. 6. From Fig. 6, there are two teams that do not belong to any conference, and these tend to be grouped with the team with which they are most closely associated. Thus, they are divided into the other ten teams. At the same time, several members are divided into other teams falsely. Although there are some differences with the real alliance, from the angle of the links of reality games, the experimental result is also reasonable.

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. (color online) Ten non-overlapping communities of college football network.

In order to further verify the performance of our algorithm, we have applied it to a number of test-case networks that are commonly used for efficiency comparisons (see Table 2). This Table gives the performances of other algorithms and our algorithm for detecting community structures in networks of various sizes. For each algorithm/network, the Table displays the modularity that is achieved and the computation time. EM-BOAD^[7] is a method of detecting overlapping communities by the seed community in weighted networks. In order to make a comparison with our method effectively, we set the weight of every edge as 1. The local optimization fitness method LFM^[18] is evaluated and analyzed by EQ.^[23] A method of label propagation algorithm SLPA^[28] is also used in this paper. For the same division result, there is little difference between these two values of modularity. As we can see from Table 2, our algorithm has better efficiency in either modularity or running time.

Table 2.

Table 2.

Table 2. Execution time and modularity on some real-world networks. . Karate Dolphin Football Power grid Cond-mat-2003a Nodes/Edges 36/78 62/159 116/615 4951/6594 31163/120029 EM-BOAD 0.331/0 s 0.493/0 s 0.578/0 s 0.796/15 s 0.46/180 s GN 0.36/0.4 0.457/2.8 s 0.585/95 s – 0.428/1305 s LFM 0.559/0.1 s 0.875/0.2 s 0.423/0.4 s 0.755/93 s 0.802/11632 s SLPA 0.359/0 s 0.417/0 s 0.538/0.2 s 0.789/3.5 s 0.65/55.6 s DOCBVA 0.332/0 s 0.511/0 s 0.596/0 s 0.815/4 s 0.645/130 s a In order to compare with our algorithms, cond-mat-2003 used here is unweighted.

Table 2. Execution time and modularity on some real-world networks. .

To further verify the performance of the algorithm, we also apply the DOCBVA to the artificial networks. Figure 7 shows the results of the experiment. 10 kinds of networks are randomly generated, each of which is executed 10 times to obtain 100 values. Each value in Fig. 7 is the mean time of the 100 values. From Fig. 7, we can get the results that the run time of our algorithm is less than other algorithms and the performance is higher. With the increase of the mixing parameter μ, the running time has a remarkable increase, but it is still in the acceptable range.

Fig. 7.

Figure Option ViewDownloadNew Window

Fig. 7. (color online) The execution time of our method on artificial networks. (a) N is the number of nodes, γ is the minus exponent for the degree sequence, β is the minus exponent for the community size distribution, μ is the mixing parameter, and ⟨k⟩ is the average degree of network. (b) The used networks are LFR benchmark graphs[23] with mixing parameter of 0.1, average degree of 15, maximum degree of 50, minimum degree of 20, exponent for the degree distribution of 2, and exponent for the community size distribution of 1.

To measure the similarity of ground truth communities and found communities, we use normalized mutual information (NMI), an information theoretic similarity measure. In order to measure the performance of overlapping communities, we use the extensional NMI realized by Eustace et al.^[29,32] The adjusted rand index (ARI)^[30–32] is also used in our method. Similar to NMI, the value of ARI is also in the range between 0 and 1. Two partitions are mutually independent when ARI is close to 0 and vice versa.^[33–35] The results are shown in Figs. 8 and 9. From the figures, we can draw a conclusion that the proposed method gives good results, especially for large size systems.

Fig. 8.

Figure Option ViewDownloadNew Window

Fig. 8. (color online) Test of our algorithm on the LFR benchmark. The number of nodes is N = 1000, γ is the exponent for the degree distribution, β is the exponent for the community size distribution, and ⟨k⟩ is the average degree. Although not shown in the figure, the average number of overlapping nodes is 10 in all networks. We use two standards NMI (top) and ARI (bottom) simultaneously to measure the detected performance.

Fig. 9.

	Figure Option ViewDownloadNew Window
	Fig. 9. (color online) Test of our algorithm on the LFR benchmark. The number of nodes is N = 5000. Two standards NMI (top) and ARI (bottom) are used simultaneously to measure the detected performance.

Table 3.

Table 3.

Table 3. The overlap coverage of our method test on the LFR benchmark. . n on μ 0.1 0.2 0.3 0.4 c0.5 0.6 1000 10 11/0.7 9/4.7 2/0.2 1/0.1 1/0.1 1/0.1 5000 50 20/11.3 31/18.4 9/7.5 1/0.1 1/0.1 0/0

Table 3. The overlap coverage of our method test on the LFR benchmark. .

Table 3 gives the overlap coverage of our method. In the generated networks, the numbers of nodes (n) are set as 1000 and 5000. The mixing parameters μ ranges from 0.1 to 0.6. The numbers of the overlapping nodes are set as 10 and 50, respectively. The maximum and average numbers of overlapping nodes are obtained, respectively. As show in Table 3, our algorithm can detect the overlapping nodes effectively.